Multi-Core Ant Colony Optimization for TSP in Scala

This is a continuation of Parallel Ant Colony Optimization for TSP in Standard ML, Multi-Core Ant Colony Optimization for TSP in Haskell, and Multi-Core Ant Colony Optimization for TSP in Erlang. See first page for Ant Colony and TSP problem description. Here the program has been rewritten in the programming language Scala.

Scala is a hybrid functional and object-oriented programming language. It is based on the Java JVM, so it has available Just-in-Time (JIT) native compilation and native thread support. It has access to the wide variety of class libraries available for Java.

Like Erlang, Scala supports an Actor-style message-passing concurrency model. More traditional thread-based concurrency with locks and shared memory is also available. Unlike Erlang and Haskell, Scala values are not immutable. Like SML and Haskell, typing is static with type inference.

Environment

All tests performed on Intel Core2 Quad CPU 2.4 GHz, 2 GB memory.
All on Debian Linux quad 2.6.22-3-686 #1 SMP Sun Feb 10 20:20:49 UTC 2008 i686
except Scala, which was tested on same machine running Windows Vista SP1, because I didn't want to deal with replacing GNU Java with Sun Java. Scala wasn't happy with GNU Java.

Versions

All from Debian apt-get, except Scala. Java from Sun.
Erlang 5.6.2
GHC Haskell 6.8.2
MLton SML 20070826
Alice SML 1.4
OCaml 3.10.2
Scala 2.7.1.final
java version "1.6.0_10-beta"
Java(TM) SE Runtime Environment (build 1.6.0_10-beta-b23)
Java HotSpot(TM) Client VM (build 11.0-b11, mixed mode, sharing)

Command Lines

mlton mlton_ant.sml
time ./mlton_ant 1 5 1000 200        (result *4)

alicec ant.sml
alicerun ant 1 5 1000 200 0          (result *4)

ghc --make -threaded -O2 ant.hs
time ./ant 1 1000 +RTS -K500m -H1000m -N1
time ./ant 1 1000 +RTS -K500m -H1000m -N2
time ./ant 1 1000 +RTS -K500m -H1000m -N3
time ./ant 1 1000 +RTS -K500m -H1000m -N4

scalac -optimize Ant.scala
scala Ant serial
scala Ant

erl -smp enable +S 1 -pa .
c(ant).
timer:tc(ant,parallelMain,[]).
erl -smp enable +S 2 -pa .
erl -smp enable +S 3 -pa .
erl -smp enable +S 4 -pa .

ocamlopt -o ant unix.cmxa ant.ml
time ./ant 1 5 1000 200

Results

Erlang and Alice SML omitted from graph. Note change from previous tests: 1000 interations, instead of 100. Still 200 cities.

Cores   Erlang   Haskell   Scala   OCaml   MLton_SML  Alice_SML
1       372      86        41.6            6.0        676
2       192      63
3       141      58
4       98       54        14.6    1.6
All times in seconds.

Code

Erlang
Haskell
MLton Standard ML
Alice Standard ML
Scala
OCaml: forking implemention posted by Jon Harrop to comp.lang.functional

Blog

Previous discussions in comments in post1, post2, and (possibly :-) new post3.

Update

Added Ant Colony Optimization for TSP in Psyco Python.